/*
 * @lc app=leetcode.cn id=887 lang=cpp
 *
 * [887] 鸡蛋掉落
 */

// @lc code=start
// class Solution {
//     unordered_map<int, int> memo;
//     int dp(int k, int n) {
//         if (memo.find(n * 100 + k) == memo.end()) {
//             int ans;
//             if (n == 0) {
//                 ans = 0;
//             } else if (k == 1) {
//                 ans = n;
//             } else {
//                 int lo = 1, hi = n;
//                 while (lo + 1 < hi) {
//                     int x = (lo + hi) / 2;
//                     int t1 = dp(k - 1, x - 1);
//                     int t2 = dp(k, n - x);

//                     if (t1 < t2) {
//                         lo = x;
//                     } else if (t1 > t2) {
//                         hi = x;
//                     } else {
//                         lo = hi = x;
//                     }
//                 }

//                 ans = 1 + min(max(dp(k - 1, lo - 1), dp(k, n - lo)), max(dp(k - 1, hi - 1), dp(k, n - hi)));
//             }

//             memo[n*100 + k] = ans;
//         }
//         return memo[n * 100 + k];
//     }
// public:
//     int superEggDrop(int k, int n) {
//         return dp(k, n);
//     }
// };


class Solution {
public:
    int superEggDrop(int k, int n) {
        if (n == 1) return 1;
        vector<vector<int> > f(n + 1, vector<int>(k + 1));
        for (int i = 1; i <= k; ++i) {
            f[1][i] = 1;
        }
        int ans = -1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= k; ++j) {
                f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];
            }
            if (f[i][k] >= n) {
                ans = i;
                break;
            }
        }
        return ans;
    }
};
// @lc code=end

